The present invention relates generally to computer systems, and specifically to devices and methods for direct memory access (DMA) in such systems.
Direct memory access (DMA) is an efficient means for transferring data to and from a memory without direct involvement of a central processing unit (CPU). A DMA engine performs the desired data transfer operations as specified by DMA commands, known as descriptors. The descriptors typically indicate, for each operation, a source address from which to read the data, and a destination address to which the data are to be written. The descriptors are commonly organized in memory as a linked list, or chain, in which each descriptor contains a field indicating the address in the memory of the next descriptor to be executed. The last descriptor in the list has a null pointer in the xe2x80x9cnext descriptorxe2x80x9d field, indicating to the DMA engine that there are no more commands to be executed, and DMA should become idle once it has reached the end of the chain.
In order to initiate a chain of DMA data transfers, an application program running on a CPU prepares the appropriate chain of descriptors in a memory accessible to the DMA engine. The CPU then sends a message to the DMA engine indicating the memory address of the first descriptor in the chain, which is a request to the DMA engine to start execution of the descriptors. The application typically sends the message to the xe2x80x9cdoorbellxe2x80x9d of the DMA enginexe2x80x94a control register with a certain bus address that is specified for this purpose. Sending such a message to initiate DMA execution is known as xe2x80x9cringing the doorbellxe2x80x9d of the DMA engine. The DMA engine responds by reading and executing the first descriptor. It then updates a status field of the descriptor to indicate to the application that the descriptor has been executed. The engine follows the xe2x80x9cnextxe2x80x9d field through the entire linked list, marking each descriptor as executed, until it reaches the null pointer in the last descriptor. After executing the last descriptor, the DMA engine becomes idle and is ready to receive a new list for execution.
While the DMA engine is executing one chain, the application program may prepare a new chain for execution. This situation occurs frequently in computer network applications, in which DMA is used to transfer newly-arrived data from an incoming connection, such as an Ethernet link, to the computer""s local memory, or from the memory to an outgoing connection. When the new chain is ready, the program can, in principle, link it to the previous chain, which is already in execution by the DMA engine, by modifying the xe2x80x9cnextxe2x80x9d field in the last descriptor of the previous chain so that it points to the first descriptor in the new chain. The problem with this approach is that by the time the application has updated the xe2x80x9cnextxe2x80x9d field of the last descriptor, the DMA engine may have already read this descriptor. (This case is particularly likely to occur in modern DMA engines, which use pipeline architectures to pre-fetch, read and process multiple descriptors at once.) In such a case, the DMA engine will not notice that the last descriptor has been updated, and it will therefore simply go idle after executing this last descriptor without reading the first descriptor in the new chain.
In order to avoid such a situation, the application program must generally synchronize its operation with the DMA engine each time it submits (or appends) a new chain of descriptors. One approach to synchronization is for the program to wait until the DMA engine has become idle before ringing its doorbell to notify it of the new chain. For example, the program may check periodically to determine when the DMA engine has flagged the last descriptor in the previous chain as having been executed as a sign that the engine is idle. The program must make sure that the engine has actually become idle before it rings the doorbell again, because of the inherent limitations of the doorbell as a hardware resource. If the doorbell rings before the previous chain has finished executing, the DMA engine will presumably ignore it. An explicit synchronization mechanism is typically needed in order to avoid this situation, since the application software typically prepares new descriptors at a pace that is different from the rate of execution of the descriptors by the DMA engine.
As an addition possibility, the program may check the earlier descriptors in the previous chain to see when they are flagged, so as to judge how far the DMA engine may be from the end of the chain. If the engine is far from the end of the chain, the program will presumably have time to update the xe2x80x9cnextxe2x80x9d field of the last descriptor before it is read by the DMA engine. This approach is risky, however, in view of the pre-fetch and pipelining capabilities of advanced DMA engines mentioned above. It also requires that the same software process be used both to create the descriptor lists and to track their completion status.
Thus, there is inherent inefficiency in the design of DMA engines known in the art. The possible synchronization processes described above are time-consuming and add overhead to application program operations. Furthermore, waiting for the DMA engine to become idle requires that the DMA pipeline be flushed, which wastes DMA resources and impacts negatively on its performance. In order to minimize the relative burden of synchronization overhead, the application software can be made to prepare longer lists of descriptors before ringing the doorbell. This approach, however, has the added disadvantage of increasing the latency of data transfer service.
It is an object of the present invention to provide improved methods and devices for direct memory access (DMA).
It is a further object of some aspects of the present invention to provide an improved DMA doorbell mechanism.
In preferred embodiments of the present invention, a DMA engine is provided with a doorbell whose resources are substantially unlimited, in the sense that the doorbell may be rung multiple times without loss of data and without executing the same descriptor multiple times. When an application program prepares a new chain of descriptors for execution by the DMA engine, it modifies the xe2x80x9cnextxe2x80x9d field in the last descriptor of the preceding chain so as to point to the first descriptor in the new chain, and then it rings the doorbell. Whenever the doorbell is rung, the DMA engine sets a flag, or if the flag is already set, it leaves the flag unchanged. When the engine reaches the point of executing the last descriptor in its current chain, and it finds that the doorbell flag is set, the engine rereads the xe2x80x9cnextxe2x80x9d field of the last descriptor in order to determine whether it has been changed to point to a new chain. Only when the xe2x80x9cnextxe2x80x9d field still contains a null pointer upon rereading does the DMA engine go idle and clear the doorbell.
This new type of doorbell, as provided by preferred embodiments of the present invention, relieves the application software entirely of the need to synchronize its activities with the state of the DMA engine. It allows an existing chain of DMA descriptors to be extended reliably regardless of the state of the DMA engine itself. Thus, the performance of the software is improved, due to the elimination of synchronization overhead. The performance of the DMA engine is enhanced, as well, since there is never a need to wait for the engine to go idle before starting a new chain of descriptors. As a result, the latency of DMA service is minimized.
Although preferred embodiments are described herein with reference to DMA operations, the principles of the present invention may be extended to the more general case of synchronizing between processes of other types. These principles are applicable, for example, in situations in which a first process prepares a worklist for second process, and then rings a doorbell to alert the second process. Based on the doorbell mechanism of the present invention, the first process may extend the worklist arbitrarily, with the assurance that when the second process reaches the end of the worklist, it will look again at the last command before going idle.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a method of direct memory access (DMA), including:
receiving a first notification at a DMA engine that a first list of descriptors has been prepared, each of the descriptors in the list including an instruction for execution by the DMA engine and a link to a succeeding one of the descriptors, except for a final descriptor in the list, which has a null link;
reading and executing the descriptors in the first list using the DMA engine;
receiving a second notification at the DMA engine that a second list of the descriptors has been prepared;
rereading at least a part of the final descriptor in the first list to determine a changed value of the link, indicating to the DMA engine a first descriptor in the second list; and
reading and executing the descriptors in the second list using the DMA engine responsive to the changed value of the link.
Preferably, receiving the first and second notifications includes receiving the notifications that the first and second lists have been stored at respective addresses in a memory, and reading the descriptors includes reading the descriptors from the memory. Further preferably, executing the descriptors includes marking each of the descriptors as having been executed after executing each of the descriptors, and marking each of the descriptors includes marking the final descriptor in a manner that is distinctive from the marking of the other descriptors. Most preferably, the method includes reclaiming the addresses in the memory responsive to the marking of each of the descriptors, so as to permit reallocation of the addresses, while preserving the final descriptor from being reclaimed responsive to its distinctive marking.
Additionally or alternatively, the link in each of the descriptors includes a pointer to the address of the succeeding one of the descriptors, and receiving the second notification includes receiving the second notification after the value of the null link has been changed to include a pointer to the first descriptor in the second list.
Further additionally or alternatively, receiving the second notification includes receiving the second notification while the DMA engine is executing the descriptors in the first list, and reading and executing the descriptors in the second list includes reading and executing the descriptors responsive to the notification after the DMA engine has finished executing the descriptors in the first list. Preferably, receiving the first notification includes receiving a first data input to a command register of the DMA engine and setting a flag in response to the first data input, responsive to which flag the DMA engine reads and executes the descriptors, and receiving the second notification includes leaving the flag set as long as the DMA engine is executing the descriptors.
In a preferred embodiment, receiving the second notification includes receiving the second notification after the DMA engine has finished executing the descriptors in the first list, and rereading at least the part of the final descriptor includes rereading at least the part of the final descriptor after the final descriptor has been executed.
Typically, reading and executing the descriptors includes at least one of conveying data from a data source to a memory and conveying data from a memory to a data target. In a preferred embodiment, receiving the first and second notifications includes receiving the notifications submitted by a program running on a central processing unit (CPU), which has prepared the lists of descriptors, while conveying the data includes transmitting the data using the DMA engine substantially without intervention of the CPU in conveying the data. Preferably, receiving the second notification includes receiving the notifications submitted by the program substantially irrespective of an execution state of the DMA engine.
There is also provided, in accordance with a preferred embodiment of the present invention, a method of direct memory access (DMA), including:
preparing a first list of descriptors for execution by a DMA engine, each of the descriptors in the list including an instruction for execution by the DMA engine and a link to a succeeding one of the descriptors, except for a final descriptor in the list, which has a null link;
submitting a first notification to the DMA engine that the first list has been prepared, so that the DMA engine will execute the descriptors in the first list responsive to the first notification;
preparing a second list of the descriptors for execution by the DMA engine;
modifying the link in the final descriptor in the first list so as to indicate a first descriptor in the second list;
submitting a second notification to the DMA engine that the second list has been prepared, so that the DMA engine will execute the descriptors in the second list responsive to the second notification, substantially irrespective of an execution state of the DMA engine when it receives the second notification.
Preferably, submitting the second notification includes causing the DMA engine to reread at least a portion of the final descriptor in the first list so as to locate thereby the first descriptor in the second list.
Additionally or alternatively, preparing the first and second lists includes storing the lists at respective addresses in a memory, and submitting the first and second notifications includes notifying the DMA engine that it should read the descriptors from the memory. Preferably, the link in each of the descriptors includes a pointer to the address of the succeeding one of the descriptors, and modifying the link includes changing a value of the null link so as to include a pointer to the first descriptor in the second list.
Typically, submitting the second notification includes submitting the second notification while the DMA engine is executing the descriptors in the first list. Alternatively, submitting the second notification includes submitting the second notification after the DMA engine has finished executing the descriptors in the first list.
There is additionally provided, in accordance with a preferred embodiment of the present invention, apparatus for direct memory access (DMA), including a DMA engine, which is coupled to receive a first notification that a first list of descriptors has been prepared, each of the descriptors in the list including an instruction for execution by the DMA engine and a link to a succeeding one of the descriptors, except for a final descriptor in the list, which has a null link, and which is adapted to read and execute the descriptors in the first list, and which is further coupled to receive a second notification a second list of the descriptors has been prepared, and which is further adapted to reread at least a part of the final descriptor in the first list to determine a changed value of the link, indicating a first descriptor in the second list, and to read and execute the descriptors in the second list using the DMA engine responsive to the changed value of the link.
Preferably, the apparatus includes a memory, which is coupled to store the first and second lists, wherein the first and second notifications include notifications that the first and second lists have been stored at respective addresses in a memory, and wherein the DMA engine is coupled to read the descriptors from the memory. In a preferred embodiment, the apparatus includes a processor, which is coupled to reclaim the addresses of the descriptors in the memory responsive to the indication that the descriptors have been executed, so as to permit reallocation of the addresses, while preserving the final descriptor from being reclaimed responsive to its distinctive indication.
Preferably, the DMA engine includes a command register and flag, wherein the first notification includes a first data input to the command register, and wherein the second notification includes a second data input to the command register, and wherein the DMA engine is adapted to set the flag in response to the first data input, and to read and execute the descriptors responsive to the flag being set, leaving the flag set as long as the DMA engine is executing the descriptors.
Typically, in accordance with the descriptors, the DMA engine performs at least one of conveying data from a data source to a memory and conveying data from a memory to a data target. In a preferred embodiment, the apparatus includes a central processing unit (CPU), which is programmed to prepare the first and second lists of descriptors and to submit the first and second notifications, responsive to which the DMA engine is adapted to convey the data substantially without intervention of the CPU in conveying the data.
There is further provided, in accordance with a preferred embodiment of the present invention, apparatus for direct memory access (DMA), including:
a DMA engine, adapted to transfer data between a data target and a data source responsive to descriptors submitted thereto; and
a descriptor processor, adapted to prepare a first list of the descriptors for execution by the DMA engine, each of the descriptors in the list including an instruction for execution by the DMA engine and a link to a succeeding one of the descriptors, except for a final descriptor in the list, which has a null link, and coupled to submit a first notification to the DMA engine that the first list has been prepared, so that the DMA engine will execute the descriptors in the first list responsive to the first notification, and which is further adapted to prepare a second list of the descriptors for execution by the DMA engine and to modify the link in the final descriptor in the first list so as to indicate a first descriptor in the second list, and which is further coupled to submit a second notification to the DMA engine that the second list has been prepared, causing the DMA engine to execute the descriptors in the second list responsive to the second notification, substantially irrespective of an execution state of the DMA engine when it receives the second notification.
The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings in which: